
#include "alloc.h"
#include <string.h>
#include "xml.h"
#define LOG_TAG "XmlItem"
#include "log.h"

/********************** XmlItemList ****************************/

#define XML_SUB_SIZE 4
#define XML_DIFF_SIZE 4

typedef struct {
    XmlItem *add;   // 新增的标签
    XmlItem *del;   // 删除的标签
    int count;      // 标签个数
} *XmlItemDiffList, XmlItemDiffListEty;

void XmlItemListAdd(XmlItemList lst, XmlItem xml)
{
    // 异常场景处理
    if (xml == NULL) return;
    // 申请内存
    if (lst->list == NULL) {
        lst->list = malloc_ct(XmlItem, XML_SUB_SIZE);
        if (lst->list == NULL) {
            LOGE("Memory exhausted");
            XmlItemFree(xml);
            return;
        }
        lst->count = 0;
    } else if ((lst->count + 1) % XML_SUB_SIZE == 0) {
        void *tmp = malloc_ct(XmlItem, lst->count + 1 + XML_SUB_SIZE);
        if (tmp == NULL) {
            LOGE("Memory exhausted");
            XmlItemFree(xml);
            return;
        }
        memcpy(tmp, lst->list, sizeof(XmlItem) * lst->count);
        free_ct(lst->list);
        lst->list = (XmlItem*) tmp;
    }

    lst->list[lst->count] = xml;
    lst->count++;
}

XmlItem XmlItemListGet(XmlItemList lst, String name)
{
    int i;
    for (i = 0; i < lst->count; i++) {
        if (StringEqual(&lst->list[i]->name, name)) {
            return lst->list[i];
        }
    }
    LOGE("%s(%d): <%.*s> not find", __func__, __LINE__, name->len, name->ptr);
    return NULL;
}

static void XmlItemDiffListAdd(XmlItemDiffList diff, XmlItem add, XmlItem del)
{
    // 申请内存
    if (diff->add == NULL) {
        diff->add = malloc_ct(XmlItem, XML_DIFF_SIZE * 2);
        if (diff->add == NULL) {
            LOGE("Memory exhausted");
            return;
        }
        diff->del = diff->add + XML_DIFF_SIZE;
        diff->count = 0;
    } else if ((diff->count + 1) % XML_DIFF_SIZE == 0) {
        XmlItem *tmp = malloc_ct(XmlItem, (diff->count + 1 + XML_DIFF_SIZE) * 2);
        if (tmp == NULL) {
            LOGE("Memory exhausted");
            return;
        }
        memcpy(tmp, diff->add, sizeof(XmlItem) * diff->count);
        memcpy(tmp + diff->count + 1 + XML_DIFF_SIZE, diff->del, sizeof(XmlItem) * diff->count);
        free_ct(diff->add);
        diff->add = tmp;
        diff->del = tmp + diff->count + 1 + XML_DIFF_SIZE;
    }

    diff->add[diff->count] = add;
    diff->del[diff->count] = del;
    diff->count++;
}

static void XmlItemDiffListFree(XmlItemDiffList diff)
{
    free_ct(diff->add);
    diff->add = NULL;
    diff->del = NULL;
    diff->count = 0;
}

static void XmlItemDiffListAddAll(XmlItemDiffList diff, XmlItem *add, int addCount, XmlItem *del, int delCount)
{
    while (addCount > 0 && delCount > 0) {
        // 使用标签名,尽量寻找相似标签并对应
        if (addCount != delCount && !StringEqual(&add[0]->name, &del[0]->name)) {
            if (addCount > delCount && StringEqual(&add[1]->name, &del[0]->name)) {
                XmlItemDiffListAdd(diff, *add, NULL);
                add++, addCount--;
                continue;
            } else if (addCount < delCount && StringEqual(&add[0]->name, &del[1]->name)) {
                XmlItemDiffListAdd(diff, NULL, *del);
                del++, delCount--;
                continue;
            }
        }

        XmlItemDiffListAdd(diff, *add, *del);
        add++, addCount--;
        del++, delCount--;
    }

    while (addCount > 0) {
        XmlItemDiffListAdd(diff, *add, NULL);
        add++, addCount--;
    }
    while (delCount > 0) {
        XmlItemDiffListAdd(diff, NULL, *del);
        del++, delCount--;
    }
}

static void XmlItemListDiff(XmlItemList baseItems, XmlItemList newItems, XmlItemDiffList diff)
{
    int i, j;
    for (i = j = 0; (i < baseItems->count) && (j < newItems->count); i++, j++) {
        if (XmlItemEqual(baseItems->list[i], newItems->list[j])) {
            continue;
        }

        // 以最小变化优先进行匹配
        int d, k;
        int dMax = (baseItems->count - i - 1) + (newItems->count - j - 1);
        for (d = 1; d <= dMax; d++) {
            for (k = 0; k <= d; k++) {
                if ((j + (d - k)) >= newItems->count) {
                    k = d - (newItems->count - j);
                    continue;
                }
                if ((i + k) >= baseItems->count) {
                    break;
                }
                if (XmlItemEqual(baseItems->list[i + k], newItems->list[j + (d - k)])) {
                    break;
                }
            }
            if ((k <= d) && ((i + k) < baseItems->count)) {
                // 说明 XmlItemEqual()==true
                break;
            }
        }
        if (d > dMax) {
            // 说明没有后续没有相同元素
            break;
        }

        XmlItemDiffListAddAll(diff, newItems->list + j, d - k, baseItems->list + i, k);
        i += k;
        j += d - k;
    }

    XmlItemDiffListAddAll(diff, newItems->list + j, newItems->count - j, baseItems->list + i, baseItems->count - i);
}

static bool hasDiffFreeVal(XmlItem xml, XmlItem xml2) {
    if (!xml->hasFreeVal && !xml2->hasFreeVal) {
        return false;
    } else if (xml->hasFreeVal != xml2->hasFreeVal) {
        return true;
    } else if (xml->sub.count != xml2->sub.count) {
        return true;
    }

    int i;
    const char *freeVal1 = xml->val.ptr;
    const char *freeVal2 = xml2->val.ptr;
    for (i = 0; i < xml->sub.count; i++) {
        String r1 = &xml->sub.list[i]->range;
        String r2 = &xml2->sub.list[i]->range;
        int len1 = (int) (r1->ptr - freeVal1);
        int len2 = (int) (r2->ptr - freeVal2);

        if (len1 != len2) return true;
        if (len1 != 0 && memcmp(freeVal1, freeVal2, len1) != 0) {
            return true;
        }

        freeVal1 = r1->ptr + r1->len;
        freeVal2 = r2->ptr + r2->len;
    }

    int len1 = (int) (xml->val.ptr + xml->val.len - freeVal1);
    int len2 = (int) (xml2->val.ptr + xml2->val.len - freeVal2);
    if (len1 != len2) return true;
    if (len1 != 0 && memcmp(freeVal1, freeVal2, len1) != 0) {
        return true;
    }
    return false;
}

void XmlItemDiff(XmlItemList baseItems, XmlItemList newItems, XmlItemList diff)
{
    XmlItemDiffListEty diffList = {NULL, NULL, 0};
    XmlItemListDiff(baseItems, newItems, &diffList);
    if (diffList.count <= 0) return;

    int i;
    for (i = 0; i < diffList.count; i++) {
        if (diffList.add[i] == NULL) {
            continue;
        }
        if (diffList.del[i] != NULL &&
            StringEqual(&diffList.add[i]->name, &diffList.del[i]->name) &&
            StringMapEqual(&diffList.add[i]->attr, &diffList.del[i]->attr) &&
            !hasDiffFreeVal(diffList.add[i], diffList.del[i])) {
            // 父标签属性相同，递归子标签
            XmlItemDiff(&diffList.del[i]->sub, &diffList.add[i]->sub, diff);
            continue;
        }
        XmlItemListAdd(diff, diffList.add[i]);
    }
    XmlItemDiffListFree(&diffList);
}

/********************** XmlItem ****************************/

void SetXmlStringEnd(String str)
{
    const unsigned char *ptr = (const unsigned char*)str->ptr;
    int i;
    for (i = 0; i < str->len; i++) {
        if (ptr[i] <= ' ') {
            break;
        } else if (ptr[i] == '>') {
            break;
        } else if (ptr[i] == '/' && ptr[i + 1] == '>') {
            break;
        }
    }
    str->len = i;
    return;
}

void XmlItemPauseAttr(XmlItem xml, Input in)
{
    StringEty key, val;
    Input2String(in, &key);
    key.len = StringIndex(&key, '=');
    if (key.len < 0) {
        LOGE("%s(%d): Attribute can't find '='", __func__, __LINE__);
        in->begin = in->end;
        return;
    }
    SetXmlStringEnd(&key);
    in->begin += key.len;

    InputSkipSpace(in);
    if (in->ptr[in->begin] != '=') {
        LOGW("%s(%d): Attribute(%.*s) can't find '='", __func__, __LINE__, key.len, key.ptr);
        StringSet(&val, "");
        StringMapPut(&xml->attr, &key, &val);
        return;
    }
    in->begin++;

    InputSkipSpace(in);
    if (in->ptr[in->begin] == '"') {
        in->begin++;
        Input2String(in, &val);
        val.len = StringIndex(&val, '"');
        if (val.len < 0) {
            LOGE("%s(%d): Attribute can't find '\"'", __func__, __LINE__);
            in->begin = in->end;
            return;
        }
        in->begin += val.len + 1;
    } else if (in->ptr[in->begin] == '\'') {
        in->begin++;
        Input2String(in, &val);
        val.len = StringIndex(&val, '\'');
        if (val.len < 0) {
            LOGE("%s(%d): Attribute can't find '''", __func__, __LINE__);
            in->begin = in->end;
            return;
        }
        in->begin += val.len + 1;
    } else {
        Input2String(in, &val);
        SetXmlStringEnd(&val);
        in->begin += val.len;
    }

    StringMapPut(&xml->attr, &key, &val);
    return;
}

void XmlItemPauseNote(XmlItem xml, Input in)
{
    in->begin++;
    Input2String(in, &xml->name);
    if (xml->name.ptr[1] == '-' && xml->name.ptr[2] == '-') {
        xml->name.len = 3;
    } else {
        SetXmlStringEnd(&xml->name);
    }
    in->begin += xml->name.len;

    Input2String(in, &xml->val);
    if (StringEqualStr(&xml->name, "!--")) {
        xml->val.len = StringSubIndex(&xml->val, StringFrom("-->"));
    } else {
        xml->val.len = StringIndex(&xml->val, '>');
    }
    if (xml->val.len < 0) {
        LOGE("%s(%d): Can't find item's end", __func__, __LINE__);
        in->begin = in->end;
        return;
    }
    in->begin += xml->val.len;

    if (StringEqualStr(&xml->name, "!--")) {
        in->begin += 3;
    } else {
        in->begin++;
    }
    return;
}

void XmlItemPauseState(XmlItem xml, Input in)
{
    in->begin++;
    Input2String(in, &xml->name);
    SetXmlStringEnd(&xml->name);
    in->begin += xml->name.len;

    InputSkipSpace(in);
    while (in->begin < in->end) {
        if (in->ptr[in->begin] == '?' && in->ptr[in->begin + 1] == '>') {
            in->begin += 2;
            return;
        }
        XmlItemPauseAttr(xml, in);
        InputSkipSpace(in);
    }

    LOGE("%s(%d): Can't find item's end", __func__, __LINE__);
    in->begin = in->end;
    return;
}

XmlItem XmlItemPause(Input in, XmlItem parent)
{
    InputSkipSpace(in);
    // 检查标签的起始符号'<'
    if (in->ptr[in->begin] != '<') {
        LOGE("%s(%d): String don't begin with '<'", __func__, __LINE__);
        in->begin = in->end;
        return NULL;
    }

    XmlItem xml = malloc_ct(XmlItemEty, 1);
    if (xml == NULL) {
        LOGE("Memory exhausted");
        in->begin = in->end;
        return NULL;
    }
    memset(xml, 0, sizeof(XmlItemEty));
    xml->parent = parent;
    StringSetBegin(&xml->range, in);

    // 解析注释和声明
    if (in->ptr[in->begin + 1] == '!') {
        XmlItemPauseNote(xml, in);
        StringSetEnd(&xml->range, in);
        return xml;
    } else if (in->ptr[in->begin + 1] == '?') {
        XmlItemPauseState(xml, in);
        StringSetEnd(&xml->range, in);
        return xml;
    }

    // 获取元素名
    in->begin++;
    Input2String(in, &xml->name);
    SetXmlStringEnd(&xml->name);
    in->begin += xml->name.len;

    // 解析元素属性
    InputSkipSpace(in);
    while (in->begin < in->end) {
        if (in->ptr[in->begin] == '>') {
            // 元素起始标签结束
            in->begin++;
            break;
        } else if (in->ptr[in->begin] == '/' && in->ptr[in->begin + 1] == '>') {
            // 标签没有内容(自闭合),直接结束
            in->begin += 2;
            StringSetEnd(&xml->range, in);
            return xml;
        }
        XmlItemPauseAttr(xml, in);
        InputSkipSpace(in);
    }

    // 解析元素内容
    StringSetBegin(&xml->val, in);
    while (in->begin < in->end) {
        InputSkipSpace(in);
        if (in->ptr[in->begin] == '<') {
            if (in->ptr[in->begin + 1] == '/') {
                // 解析到一个结束标签
                StringSetEnd(&xml->val, in);
                in->begin += 2;

                // 获取结束标签中的元素名
                StringEty str;
                Input2String(in, &str);
                SetXmlStringEnd(&str);
                // 与本元素的元素名匹配
                if (!StringEqual(&str, &xml->name)) {
                    LOGW("%s(%d): %.*s label no end", __func__, __LINE__, xml->name.len, xml->name.ptr);
                    in->begin = in->end;
                    return xml;
                }
                in->begin += str.len + 1;
                StringSetEnd(&xml->range, in);
                return xml;
            }

            // 解析到一个起始标签,解析子元素
            XmlItemListAdd(&xml->sub, XmlItemPause(in, xml));
        } else {
            xml->hasFreeVal = true;
            // 寻找下一标签的起始符号'<'
            StringEty str;
            Input2String(in, &str);
            int index = StringIndex(&str, '<');
            if (index < 0) {
                xml->val.len = (int) (in->ptr + in->end - xml->val.ptr);
                LOGW("%s(%d): %.*s item's name can't find end", __func__, __LINE__,
                    xml->name.len, xml->name.ptr);
                in->begin = in->end;
                return xml;
            }
            // 跳转到下一标签的起始位置
            in->begin += index;
        }
    }
    in->begin = in->end;
    return xml;
}

void XmlItemFree(XmlItem xml)
{
    if (xml == NULL) return;
    int i;
    for (i = 0; i < xml->sub.count; i++) {
        XmlItemFree(xml->sub.list[i]);
    }
    free_ct(xml->sub.list);
    StringMapFree(&xml->attr);
    free_ct(xml);
}

XmlItem XmlItemSub(XmlItem xml, String name)
{
    if (xml->sub.list == NULL || xml->sub.count <= 0) {
        LOGE("%s(%d): %.*s item no child", __func__, __LINE__, xml->name.len, xml->name.ptr);
        return NULL;
    }
    return XmlItemListGet(&xml->sub, name);
}

bool XmlItemValue(XmlItem xml, String val)
{
    String valTmp = StringMapGet(&xml->attr, StringFrom("value"));
    if (valTmp != NULL) {
        StringClone(val, valTmp);
        return true;
    }

    if (xml->sub.list != NULL && xml->sub.count > 0) {
        return XmlItemValue(xml->sub.list[0], val);
    }

    InputEty inTmp;
    String2Input(&xml->val, &inTmp);
    InputSkipSpace(&inTmp);
    while (inTmp.end > inTmp.begin) {
        if ((unsigned char) inTmp.ptr[inTmp.end - 1] > ' ') {
            break;
        }
        inTmp.end--;
    }
    Input2String(&inTmp, val);
    return true;
}

bool XmlItemEqual(XmlItem xml, XmlItem xml2)
{
    if (!StringEqual(&xml->name, &xml2->name)) {
        return false;
    }
    if (!StringMapEqual(&xml->attr, &xml2->attr)) {
        return false;
    }
    if (xml->hasFreeVal != xml2->hasFreeVal) {
        return false;
    }
    return StringEqual(&xml->val, &xml2->val);
}

/********************** XmlDoc ****************************/

void XmlPause(XmlDoc doc, Input in)
{
    doc->list = NULL;
    doc->count = 0;

    InputSkipBOM(in);
    while (in->begin < in->end) {
        XmlItemListAdd(doc, XmlItemPause(in, NULL));
        InputSkipSpace(in);
    }
}

void XmlFree(XmlDoc doc)
{
    int i;
    for (i = 0; i < doc->count; i++) {
        XmlItemFree(doc->list[i]);
    }
    free_ct(doc->list);
    doc->list = NULL;
    doc->count = 0;
}

bool XmlCharset(XmlDoc doc, String charset)
{
    XmlItem state = XmlItemListGet(doc, StringFrom("?xml"));
    if (state == NULL) {
        LOGE("%s(%d): <?xml ?> not find", __func__, __LINE__);
        return false;
    }

    String encode = StringMapGet(&state->attr, StringFrom("encoding"));
    if (encode == NULL) {
        LOGE("%s(%d): <?xml encoding=\"XXX\"?> not find", __func__, __LINE__);
        return false;
    }

    StringClone(charset, encode);
    return true;
}

void XmlDiff(XmlDoc doc, XmlDoc doc2, XmlItemList lst)
{
    lst->list = NULL;
    lst->count = 0;
    XmlItemDiff(doc, doc2, lst);
}
